package com.dyz.leetcode;

public class SortList148 {
    public ListNode sortList(ListNode head) {
        if(head==null|| head.next==null){return head;}
        //查下半部分
        ListNode lastNode = getLastNode(head);
        //递归
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(lastNode);

        //合并
        return merge(l1,l2);

    }
    private ListNode getLastNode(ListNode node){
        //使用快慢指针找到中间节点
        ListNode fast = node;
        ListNode slow = node;
        ListNode breakNode = node;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            breakNode = slow;
            slow = slow.next;
        }
        breakNode.next = null;
        return slow;
    }
    private ListNode merge(ListNode l1, ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if (l1.val<l2.val){
            l1.next=merge(l1.next, l2);
            return l1;
        }else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}
